"""
Problem 40: https://projecteuler.net/problem=40

Champernowne's constant

An irrational decimal fraction is created by concatenating the positive
integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the
following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/13                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
'''


def total(d: int) -> int:
    '''
    0.  1  2  3  4  5  6  7  8  9             insert 0 digit
    -----------------------------------------------------------
    10 11 12 13 14 15 16 17 18 19   +1        insert 1 digit
    20 21 22 23 24 25 26 27 28 29   +2
    ...                                       total = 2*10*9
    90 91 92 93 94 95 96 97 98 99   +9
    -----------------------------------------------------------
    100 101 102 103 ...       109   +10       insert 2 digits
    ...                                       
    990 991 992 ...           999   +99       total = 3*10*90
    -----------------------------------------------------------
    1000 1001 1002 ...       1009   +100      insert 3 digits
    ...
    9990 9991 9992 ...       9999   +999      total = 4*10*900
    -----------------------------------------------------------

    so, after inserting d digits, the total of numbers is:
        (1) if d=0, total = 9
        (2) if d>0, 
                    total = 9 + sum((i+1)*10*9*10^(i-1)), i = 1,2,...d
                          = 9 + 9*sum((i+1)*10^i)

                                   (9d+8)*10^(d+1) - 80
                          = 9 + 9* --------------------
                                           81
        when d=0, the formula is also right.
    '''
    return 9 + ((9*d+8)*(10**(d+1))-80)//9


def solution(*positions) -> int:
    positions = sorted(list(positions), reverse=True)
    bases = dict()

    def insertPositions(index):
        pos = 0
        while True:
            bases[pos] = total(pos)
            if bases[pos] < index:
                pos += 1
            else:
                break
        return pos

    inserts = [insertPositions(pos) for pos in positions]
    # print(bases, inserts)

    res = 1
    for i in range(len(positions)):
        if positions[i] <= 9:
            res *= positions[i]
            continue

        d, offset = divmod(
            positions[i] - bases[inserts[i]-1], (inserts[i]+1)*10)
        lines = d + (10**(inserts[i]-1))
        if offset == 0:
            lineStr = ''.join([str(lines-1) + str(i) for i in range(10)])
            digit = 9
        else:
            lineStr = ''.join([str(lines) + str(i) for i in range(10)])
            digit = int(lineStr[offset-1])

        res *= digit

        # print(positions[i],lines, offset, lineStr, digit)
    # if positions[-1]<10: print(positions[-1], positions[-1]) 

    return res


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution(1, 10, 100, 1000, 10000, 100000, 1000000))
    # 210

    '''
    {0: 9, 1: 189, 2: 2889, 3: 38889, 4: 488889, 5: 5888889} [5, 4, 3, 2, 1, 1, 0]

    1000000 18518 31 185180185181185182185183185184185185185186185187185188185189 1
    100000 2222 11 22220222212222222223222242222522226222272222822229 2
    10000 277 31 2770277127722773277427752776277727782779 7
    1000 37 1 370371372373374375376377378379 3
    100 5 11 50515253545556575859 5
    10 1 1 10111213141516171819 1
    '''
